#include<vector>
#include<iostream>

using namespace std;

vector<int> insertionSort(vector<int> array) {
  int i = 1;
  int j = 1;
  while (i < array.size()) {
    if (j == 0) {
      i++;
      j = i;
    }
    if (array[j - 1] > array[j]) {
      swap(array[j - 1], array[j]);
      j--;
    } else {
      i++;
      j = i;
    }
  }
  return array;
}

int main(int argc, char const *argv[]) {
  vector<int> arr = insertionSort({1, 3, 5, 0, 8, 1, 12, 2, -5});
  for (int i : arr) {
    cout << i << " ";
  }
  
  return 0;
}
